Modern computer systems employ cache memories in addition to main memory. The access latency of cache memory is significantly less than the access latency of main memory. One type of these cache memories retains recently accessed data, in the presumption that this data will be accessed again in the future. Memory operations performed by a processor will access this cache memory first. In the event that the accessed data is not found in the cache (termed a cache miss), the processor must wait for an extended period of time while that data is loaded into the cache from a slower or more remote memory. Processor stalls caused by this wait period comprise the majority of execution time for many applications.
Cache memories are logically organized as multiple sets of cache blocks. When a cache miss occurs, the set in which the new block is placed is first examined; if that set is full, room must be created for the new block by evicting one of the currently residing blocks from the set. This block selected for eviction is termed the victim. There has been much prior work described in the literature on determining the best choice of victim, such that the miss rate to the cache will be minimized. Examples of such cache block replacement policies include least-recently used (LRU) and first-in-first out (FIFO). These replacement policies have been designed to minimize the frequency of misses to the cache.
Modern languages such as Java™ or C# employ garbage collection techniques to manage memory allocation for objects. Such memory management techniques segregate allocated objects by regions, with different characteristics. For example, many programs tend to exhibit a high-rate of short-lived object allocations. Typically, only a small percentage of these allocated objects survive subsequent garbage collections. Objects that survive long-enough may be moved to another memory region.
Consequently, there are regions in memory which exhibit different reuse characteristics. The probability of reusing a cache line containing long-lived objects is typically higher. This is particularly true of generational garbage collectors, where there are separate regions for the newly allocated objects (nurseries) and long-lived objects (mature space). The concept of memory region can be applied to many other cases. For example, a region of memory could be the thread-local-heap memory (TLH), or a temporary allocation used by a thread; thus there could be multiple regions of memory at the same time.
There is a need for a cache replacement method to overcome the shortcomings of the known caches.